#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<int>> dp(row,vector<int>(col,0));
        //初始化
        dp[0][0] = grid[0][0];
        for(int i = 1;i<col;++i){
            dp[0][i] = grid[0][i]+dp[0][i-1];
        }
        for(int i = 1;i<row;++i){
            dp[i][0] = grid[i][0]+dp[i-1][0];
        }
        for(int i = 1;i<row;++i){
            for(int j = 1;j<col;++j){
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[row-1][col-1];
    }
};

int main(){
    Solution S;
    vector<vector<int>> nums = {{1,3,1},{1,5,1},{4,2,1}};
    cout<<S.maxValue(nums)<<endl;
}
